\input{defs.tex}

\author{Valeria Nikolaenko and Kevin Lewi}
\title{CS255. Project 1. Milestone 1.}

\begin{document}
\marginparsep = 10pt
\maketitle

\section{GenerateKey function}

As was shown in class, PRG $G$ can be obtained from the PRF as follows (assuming 
that AES is a secure PRF):
\begin{align}
G(k) = AES(k, 0) || AES(k, 1) || ... || AES(k, t)\\
AES: K \times \{0, 1\}^n \rightarrow \{1, 0\}^n\\
G: K \rightarrow \{0, 1\}^{nt}
\end{align}

Our implementation goes as follows: we are getting $8$ bytes of entropy when we 
are first asked for the pseudorandom bunch of bytes and use this entropy as a 
key to setup AES (in the formula above we set $k$ to be equal to entropy). We 
store the number of times the PRG was called as an array of $4$ words, starting 
from zero and incrementing it within each call. Here, We assume that the PRG 
will not be called more than $2^{128}$ times so our counter will not overflow. 
We give this counter to AES for an encryption to get the next $4$ pseudorandom 
words.

\begin{algorithm}
\caption{Function $PRG()$:}
If entropy is undefined, $entropy = GetEntropy(8)$, $AES = AES(entropy)$, 
$prgcounter = 0$.\\
Yield $AES(prgcounter)$.\\
$prgcounter++$.
\end{algorithm}

If we assume that the AES is a secure PRF, the above construction will give a 
PRG as was shown in class.

\section{Encrypt and Decrypt functions}

We have chosen to implement CTR-mode as it does not require padding and thus has 
no $1$ byte message expansion.\\
\begin{itemize}
\item Encryption\\
For the next message we are creating AES scheme with group key $k$ and nonce 
$IV$ that we are getting from PRG. We then xor block number $i$ of the message 
with $AES(k, IV + i)$ to get the block of the cipher. We prepend the whole 
cipher with an $IV$ that we've been using.
Assuming AES is a PRF we are getting CPA security, as was shown in class.\\

\item Decryption\\
Decryption is straightforward. We read the $IV$ from the beginning of the cipher 
and initialize $AES$ with the group key $k$. We then xor each block of the 
cipher with $AES(k, IV + i)$ to get the original message back again.
\end{itemize}

\section{SaveKeys and LoadKeys function}

The interaction between SaveKeys and LoadKeys is similar to that of encryption 
and decryption. However, this time, we do not have a group key to use for the 
AES encryption. But here, we request a password from the user that acts as the 
password to the database. A hashed version of this password is then used as the 
key for AES, and after this modification, SaveKeys behaves similarly to Encrypt 
and LoadKeys to Decrypt.

Let $p$ be the password that the user designates as the database password. 
Ultimately, we would like to prevent the adversary from recovering any 
information about the group keys saved in the database. Note that the database 
password, along with a salt (a string of random bits), is hashed via the 
StringToBits function, which is assumed to be a collision-resistant hash 
function. The property of a collision-resistant hash function is that the output 
is poly-time indistinguishable from random, which means that the adversary 
cannot learn anything about the input given only the output of StringToBits. In 
other words, the output of StringToBits is pseudorandom and can be used safely 
as the key to CTR-mode AES.

There is another small issue, however: note that in order for encryption and 
decryption to work, one must be able to generate the same hashed output of 
StringToBits. Thus, we require that the user remember a password, but since 
StringToBits is deterministic, it is not desirable to directly hash the 
password. Thus, we add a short random string, which we call the salt, added to 
the database password prior to being hashed by StringToBits. The salt can be 
stored in plaintext safely since it reveals nothing about the password, and yet 
it allows for the output of the hash function to be randomized.

So the scheme works as follows, utilizing CTR-mode base on AES encryption 
scheme:

\begin{algorithm}
\caption{SaveKeys}
$salt \leftarrow PRG();$\\
$hash = Hash(password + salt);$\\
Suppose $keys$ is a string representing the set of keys and $keys[i]$ is the 
$i$-th block of this string.\\
$IV \leftarrow PRG();$\\
$cipher = salt || IV || (keys[0] \oplus AES(hash, IV) || (keys[1] \oplus 
AES(hash, IV + 1) || ... || (keys[n] \oplus AES(hash, IV + n);$
\end{algorithm}

We argued that $hash$ will be unique with probability almost $1$, which is why 
CTR-mode based on AES can be considered to be secure for key storage.
(As a Hash function we are using StringToBits function, built on top of SHA256, 
from the startup code.)

\end{document}
